package com.zyk.problem;

import java.util.Stack;

/**
 * @author zhangsan
 * @date 2021/5/2 19:53
 */
public class ValidParentheses {

    // 栈
    public static boolean isValid1(String s) {
        char[] str = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length; i++) {
            if (str[i] == '(') {
                stack.push('(');
            } else {
                if (stack.isEmpty()) return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

    public static boolean isValid2(String s) {
        char[] str = s.toCharArray();
        int cnt = 0;
        for (int i = 0; i < str.length; i++) {
            if (str[i] == '(') {
                cnt++;
            } else {
                if (--cnt < 0) return false;
            }
        }
        return cnt == 0;
    }

    public static int maxNeed(String s) {
        char[] str = s.toCharArray();
        int cnt = 0, need = 0;
        for (int i = 0; i < str.length; i++) {
            if (str[i] == '(') {
                cnt++;
            } else {
                if (--cnt < 0) {
                    need++;
                    cnt = 0;
                }
            }
        }
        return cnt + need;
    }

    // for test
    public static void main(String[] args) {
        /*String str = "(())";
        System.out.println(isValid1(str));
        System.out.println(isValid2(str));*/

        /*int times = 10000;
        for (int i = 0; i < times; i++) {
            String s = generateString();
            System.out.println("=================");
            System.out.println(s);
            System.out.println(isValid1(s));
            System.out.println(isValid2(s));
            System.out.println("=================");
        }*/

        // 最少需要添多少个括号测试
        String s = ")))(((";
        System.out.println(maxNeed(s));

    }

    public static String generateString() {
        int len = (int) (Math.random() * 100);
        char[] str = new char[len];
        for (int i = 0; i < len; i++) {
            str[i] = Math.random() < 0.5 ? '(' : ')';
        }
        return new String(str);
    }

}
